public class PathWithMaximumGold {
    public static void main(String[] args) {
//        int[][] grid = {{0, 6, 0}, {5, 8, 7}, {0, 9, 0}};
        int[][] grid = {{34, 0, 1, 0, 0, 0}, {0, 0, 2, 0, 1, 0}, {5, 4, 3, 7, 4, 2}, {0, 0, 5, 0, 1, 4}, {0, 0, 5, 0, 2, 3}};
        System.out.println(getMaximumGold(grid));
    }

     int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
     int ans = 0;
     int[][] haha;
     int n;
     int m;

    public  int getMaximumGold(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        haha = grid;

        // 利用dfs深度优先，
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 0) {
                    dfs(i, j, 0);
                }
            }
        }
        return ans;
    }


    public  void dfs(int x, int y, int sum) {
        // 到当前节点往下有三个方向。
//        System.out.println("+"+grid[x][y]);
        sum += haha[x][y];
        ans = Math.max(ans, sum);

        // 先置为0进行递归
        int tmp = haha[x][y];
        haha[x][y] = 0;

        for (int[] dir : direction
        ) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            // 异常点排除或者被挖了（=0）
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || haha[nx][ny] == 0) {
                continue;
            }
            dfs(nx, ny, sum);
        }
        haha[x][y] = tmp;
    }
}